題目:
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
給定兩個非空鍊錶,分別表示兩個非負整數。數字以逆序存儲,每個節點包含一位數字。將兩個數字相加,並以鍊錶形式返回和。
您可以假設這兩個數字不包含任何前導零,除了數字 0 本身。
範例:
題目重點
兩個鏈表 l1、l2 各自代表一個非負整數。
逆序存儲:頭節點就是個位數,往後依次是十位、百位…
要返回一個新的鏈表,表示它們的和(同樣逆序)。
解題核心思路
逐位相加:
從鏈表頭(最低位)開始,把 l1.val + l2.val + carry 相加。
處理進位:
節點的值 = (sum % 10)
新的進位 = (sum / 10)
繼續往後:
l1、l2 往下一節點移動
若某個鏈表已經走到尾端,就當作 0
處理最後進位:
如果計算完畢後 carry = 1,要額外補上一個新節點。
返回結果:
使用一個虛擬頭節點(dummy head)來簡化操作,最後回傳 dummy.next。